using System;
using Microsoft.SPOT;

namespace codebase
{
    public class Inflator
    {

        private readonly int[] clcl = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 }; //code length code lengths
        private readonly int[] lengthbase = { 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258 };
        private readonly int[] lengthextra = { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0 };
        private readonly int[] distancebase = { 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577 };
        private readonly int[] distanceextra = { 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13 };

        #region Variables

        private int _error;
        private HuffmanTree codetree, codetreeD, codelengthcodetree;

        #endregion

        #region Constructor

        public Inflator()
        {
            codetree = new HuffmanTree();
            codetreeD = new HuffmanTree();
            codelengthcodetree = new HuffmanTree();
        }

        #endregion

        #region Properties

        public int Error
        {
            get { return _error; }
        }

        #endregion

        #region Public Methods

        public void Inflate(ref byte[] Scanlines, byte[] Data)
        {
            int bp = 0, pos = 0;
            _error = 0;
            int BFINAL = 0;
            int BTYPE = 0;
            while (BFINAL == 0 && _error == 0)
            {
                if (bp >> 3 >= Data.Length)
                {
                    _error = 52;
                    return;
                } //error, bit pointer will jump past memory

                BFINAL = readBitFromStream(ref bp, Data);

                BTYPE = readBitFromStream(ref bp, Data);
                BTYPE += 2 * readBitFromStream(ref bp, Data);

                if (BTYPE == 3)
                {
                    _error = 20;
                    return;
                } //error: invalid BTYPE
                else if (BTYPE == 0)
                {
                    //Debug.Print("BTYPE 0");
                    inflateNoCompression(ref Scanlines, Data, ref bp, ref pos, Data.Length);
                }
                else
                {
                    //Debug.Print("BTYPE 1 OR 2");
                    inflateHuffmanBlock(ref Scanlines, Data, ref bp, ref pos, Data.Length, BTYPE);
                }
            }
        }

        #endregion

        #region Private Methods

        private void generateFixedTrees(ref HuffmanTree tree, ref HuffmanTree treeD)
        {
            int[] bitlen, bitlenD;
            int i;

            // Setup arrays
            bitlen = new int[288];
            for (i = 0; i < 288; i++)
                bitlen[i] = 8;

            bitlenD = new int[32];
            for (i = 0; i < 32; i++)
                bitlenD[i] = 5;

            for (i = 144; i <= 255; i++)
                bitlen[i] = 9;

            for (i = 256; i <= 279; i++)
                bitlen[i] = 7;

            tree.makeFromLengths(ref bitlen, 15);
            treeD.makeFromLengths(ref bitlenD, 15);
        }

        private void getTreeInflateDynamic(ref HuffmanTree tree, ref HuffmanTree treeD, ref byte[] Data, ref int bp, int inlength)
        {
            int[] bitlen, bitlenD;
            int i;

            // Setup arrays
            bitlen = new int[288];
            //for (i = 0; i < 288; i++)
            // bitlen[i] = 0;

            bitlenD = new int[32];
            //for (i = 0; i < 32; i++)
            // bitlenD[i] = 0;

            if (bp >> 3 >= inlength - 2)
            {
                _error = 49;
                return;
            } //the bit pointer is or will go past the memory

            int HLIT = (int)readBitsFromStream(ref bp, Data, 5) + 257; //number of literal/length codes + 257
            int HDIST = (int)readBitsFromStream(ref bp, Data, 5) + 1; //number of distance codes + 1
            int HCLEN = (int)readBitsFromStream(ref bp, Data, 4) + 4; //number of code length codes + 4
            int[] codelengthcode = new int[19]; //lengths of tree to decode the lengths of the dynamic tree

            for (i = 0; i < 19; i++)
                codelengthcode[clcl[i]] = (byte)((i < HCLEN) ? readBitsFromStream(ref bp, Data, 3) : 0);

            _error = codelengthcodetree.makeFromLengths(ref codelengthcode, 7);
            if (_error != 0)
                return;

            int replength, code;
            i = 0;
            while (i < HLIT + HDIST)
            {
                code = huffmanDecodeSymbol(ref Data, ref bp, ref codelengthcodetree, inlength);
                if (_error != 0)
                    return;

                if (code <= 15)
                {
                    if (i < HLIT)
                        bitlen[i++] = code;
                    else
                        bitlenD[i++ - HLIT] = code;
                } //a length code
                else if (code == 16) //repeat previous
                {
                    if (bp >> 3 >= inlength)
                    {
                        _error = 50;
                        return;
                    } //error, bit pointer jumps past memory

                    replength = 3 + (int)readBitsFromStream(ref bp, Data, 2);
                    int value; //set value to the previous code

                    if ((i - 1) < HLIT)
                        value = bitlen[i - 1];
                    else
                        value = bitlenD[i - HLIT - 1];

                    for (int n = 0; n < replength; n++) //repeat this value in the next lengths
                    {
                        if (i >= HLIT + HDIST)
                        {
                            _error = 13;
                            return;
                        } //error: i is larger than the amount of codes
                        if (i < HLIT)
                            bitlen[i++] = value;
                        else
                            bitlenD[i++ - HLIT] = value;
                    }
                }
                else if (code == 17) //repeat "0" 3-10 times
                {
                    if (bp >> 3 >= inlength)
                    {
                        _error = 50;
                        return;
                    } //error, bit pointer jumps past memory
                    replength = 3 + (int)readBitsFromStream(ref bp, Data, 3);
                    for (int n = 0; n < replength; n++) //repeat this value in the next lengths
                    {
                        if (i >= HLIT + HDIST)
                        {
                            _error = 14;
                            return;
                        } //error: i is larger than the amount of codes
                        if (i < HLIT)
                            bitlen[i++] = 0;
                        else
                            bitlenD[i++ - HLIT] = 0;
                    }
                }
                else if (code == 18) //repeat "0" 11-138 times
                {
                    if (bp >> 3 >= inlength)
                    {
                        _error = 50;
                        return;
                    } //error, bit pointer jumps past memory
                    replength = 11 + (int)readBitsFromStream(ref bp, Data, 7);
                    for (int n = 0; n < replength; n++) //repeat this value in the next lengths
                    {
                        if (i >= HLIT + HDIST)
                        {
                            _error = 15;
                            return;
                        } //error: i is larger than the amount of codes
                        if (i < HLIT)
                            bitlen[i++] = 0;
                        else
                            bitlenD[i++ - HLIT] = 0;
                    }
                }
                else
                {
                    _error = 16;
                    return;
                } //error: somehow an unexisting code appeared. This can never happen.
            }
            if (bitlen[256] == 0)
            {
                _error = 64;
                return;
            } //the length of the end code 256 must be larger than 0
            _error = tree.makeFromLengths(ref bitlen, 15);
            if (_error != 0)
                return; //now we've finally got HLIT and HDIST, so generate the code trees, and the function is done
            _error = treeD.makeFromLengths(ref bitlenD, 15);
            if (_error != 0)
                return;

        }

        private int huffmanDecodeSymbol(ref byte[] Data, ref int bp, ref HuffmanTree codetree, int inlength)
        {
            bool decoded = false;
            int ct = 0;
            for (int treepos = 0; ; )
            {
                if ((bp & 0x07) == 0 && (bp >> 3) > inlength)
                {
                    _error = 10;
                    return 0;
                } //error: end reached without endcode
                _error = codetree.decode(ref decoded, ref ct, ref treepos, (int)readBitFromStream(ref bp, Data));
                if (_error != 0)
                    return 0; //stop, an error happened
                if (decoded)
                    return ct;
            }
        }

        private void inflateHuffmanBlock(ref byte[] Scanlines, byte[] Data, ref int bp, ref int pos, int inlength, int btype)
        {
            if (btype == 1)
            {
                generateFixedTrees(ref codetree, ref codetreeD);
            }
            else if (btype == 2)
            {
                getTreeInflateDynamic(ref codetree, ref codetreeD, ref Data, ref bp, inlength);
                if (_error != 0)
                    return;

                while (true)
                {
                    int code = huffmanDecodeSymbol(ref Data, ref bp, ref codetree, inlength);
                    if (_error != 0)
                        return;

                    if (code == 256)
                        return; //end code
                    else if (code <= 255) //literal symbol
                    {
                        if (pos >= Scanlines.Length)
                        {
                            //reserve more room
                            byte[] tmp = new byte[(pos + 1) * 2];
                            Array.Copy(Scanlines, tmp, Scanlines.Length);
                            Scanlines = tmp;
                            tmp = null;
                        }
                        Scanlines[pos++] = (byte)(code);
                    }
                    else if (code >= 257 && code <= 285) //length code
                    {
                        int length = (int)lengthbase[code - 257], numextrabits = (int)lengthextra[code - 257];
                        if ((bp >> 3) >= inlength)
                        {
                            _error = 51;
                            return;
                        } //error, bit pointer will jump past memory

                        length += (int)readBitsFromStream(ref bp, Data, numextrabits);

                        int codeD = huffmanDecodeSymbol(ref Data, ref bp, ref codetreeD, inlength);
                        if (_error != 0)
                            return;

                        if (codeD > 29)
                        {
                            _error = 18;
                            return;
                        }

                        int distance = distancebase[codeD], numextrabitsD = distanceextra[codeD];
                        if ((bp >> 3) >= inlength)
                        {
                            _error = 51;
                            return;
                        } //error, bit pointer will jump past memory

                        distance += (int)readBitsFromStream(ref bp, Data, numextrabitsD);

                        int start = pos, backward = start - distance;

                        if (pos + length >= Scanlines.Length)
                        {
                            //reserve more room
                            byte[] tmp = new byte[(pos + length) * 2];
                            Array.Copy(Scanlines, tmp, Scanlines.Length);
                            Scanlines = tmp;
                            tmp = null;
                        }

                        for (int forward = 0; forward < length; forward++)
                        {
                            Scanlines[pos++] = Scanlines[backward++];
                            if (backward >= start)
                                backward = start - distance;
                        }
                    }
                }
            }
        }

        private void inflateNoCompression(ref byte[] Scanlines, byte[] Data, ref int bp, ref int pos, int inlength)
        {
            while ((bp & 0x7) != 0)
                bp++; //go to first boundary of byte
            int p = bp / 8;
            if (p >= inlength - 4)
            {
                _error = 52;
                return;
            } //error, bit pointer will jump past memory
            int LEN = Data[p] + 256 * Data[p + 1], NLEN = Data[p + 2] + 256 * Data[p + 3]; p += 4;
            if (LEN + NLEN != 65535)
            {
                _error = 21;
                return;
            } //error: NLEN is not one's complement of LEN

            if (pos + LEN >= Scanlines.Length)
            {
                byte[] tmp = new byte[pos + LEN];
                Array.Copy(Scanlines, tmp, Scanlines.Length);
                Scanlines = tmp;
            }

            if (p + LEN > inlength)
            {
                _error = 23;
                return;
            } //error: reading outside of in buffer
            for (int n = 0; n < LEN; n++)
                Scanlines[pos++] = Data[p++]; //read LEN bytes of literal data
            bp = p * 8;
        }

        private int readBitFromStream(ref int bitp, byte[] bits)
        {
            int result = (int)((bits[bitp >> 3] >> (bitp & 0x7)) & 1);
            bitp++;
            return result;
        }

        private int readBitsFromStream(ref int bitp, byte[] bits, int nbits)
        {
            int result = 0;
            for (int i = 0; i < nbits; i++)
                result += (readBitFromStream(ref bitp, bits)) << i;
            return result;
        }

        #endregion

    }
}
